#include <iostream>
#include <stack>
#include "magicsquare.h"
using namespace std;


int main() {
	// initialize
	Square startPuzzle;
	stack <Square> trace; 
	trace.push(startPuzzle);

	bool done = false;
	// loop until solve problem or have to give up
	while ((! done) && ( ! trace.empty() )) {
		// try to move forward from top of the stack
		//     (make use of where has already been tried 
		//      from here to avoid looping)
		Square next = trace.top().nextNonBadSquare();
		// if can't advance
		if (next.searchAtEnd() ) {
			// pop top off stack
			// MAR - do we need to save where we were and then change the new top
			//    after popping????
			int savRow = trace.top().getFirstRowTried();  // was getLastRowTried
			int savCol = trace.top().getFirstColTried();
			int savVal = trace.top().getFirstValTried();
			trace.pop();
			if (! trace.empty() ) {
				// MAR - need below to avoid looping at end, but want 
				// to remove it to avoid looping deeper
				trace.top().setLastRowTried(savRow);
				trace.top().setLastColTried(savCol);
				trace.top().setLastValTried(savVal);
				cout << "Reconsidering at " << trace.size() << " deep"  << endl << trace.top();
				cout << "wait> ";
				char junk;
				cin >> junk;
			}
		}
		// else
		else {
			cout << "Searching " << trace.size()+1 << " deep"  << endl << next;
			cout << "wait> ";
			char stuff;
			cin >> stuff;
			// doesn't seem right
			/*
			next.setFirstRowTried(next.getFirstRowTried());
			next.setFirstColTried(next.getFirstColTried());
			next.setFirstValTried(next.getFirstValTried());
			*/
			// I think the first one tried at the next level should be the last one tried at the previous level
			next.setFirstRowTried(next.getLastRowTried()  ); // was trace.top().getLastRowTried()
			next.setFirstColTried(next.getLastColTried());
			next.setFirstValTried(next.getLastValTried());
			// add to top of stack
			trace.push(next);
			// check for done
			done = trace.top().checkSquare();
		} // endif
	} // end while
	// if got here it is either because done or had to give up
	// (can tell if had to give up if stack is empty)
	if (trace.empty() ) {
		cerr << "No solution found " << endl;
	}
	else {
		cout << "Solution found " << endl;
		cout << trace.top();
	}
	return 0;
}